package leetcode.code1017;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public String baseNeg2(int n) {
		int[] mins = new int[32];
		int[] maxs = new int[32];
		for (int i = 0, min = 0, max = 0; i < maxs.length; i++) {
			if ((i & 1) == 0) {
				max += 1 << i;
			} else {
				min -= 1 << i;
			}
			mins[i] = min;
			maxs[i] = max;
		}
		int p = 0;
		while (maxs[p] < n) {
			p++;
		}
		if (maxs[p] == n) {
			return Integer.toBinaryString(maxs[p]);
		}
		int sum = 1 << p;
		char[] ans = new char[p + 1];
		ans[ans.length - p - 1] = '1';
		for (int i = p - 1; i > 0; i--) {
			int min = mins[i - 1], max = maxs[i - 1];
			if ((i & 1) == 0) {
				int add = 1 << i;
				if (sum + add + min <= n && sum + add + max >= n) {
					sum += add;
					ans[ans.length - i - 1] = '1';
				} else {
					ans[ans.length - i - 1] = '0';
				}
			} else {
				int sub = 1 << i;
				if (sum - sub + min <= n && sum - sub + max >= n) {
					sum -= sub;
					ans[ans.length - i - 1] = '1';
				} else {
					ans[ans.length - i - 1] = '0';
				}
			}
		}
		ans[ans.length - 1] = sum + 1 == n ? '1' : '0';
		return new String(ans);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		H.compare("111", this.baseNeg2(3));
		H.compare("11010", this.baseNeg2(6));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int max = (int) 1e9;
		System.out.println(max);
		System.out.println(Integer.toBinaryString(max));
		System.out.println(Integer.toBinaryString(max).length());
	}

}
